class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for (int i = 1; i <= n*m; i ++) p[i] = i;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                int k = (m*i)+j+1;
                if (grid[i][j] == '1'){
                    if (i-1 >= 0 && grid[i-1][j] == '1' && finds(k) != finds(k-m)) p[finds(k)] = finds(k-m);
                    if (j-1 >= 0 && grid[i][j-1] == '1' && finds(k) != finds(k-1)) p[finds(k)] = finds(k-1);
                }
                else p[k] = 0;
            }
        }
        int res = 0;

        for (int i = 1; i <= n*m; i ++) {
            if (p[i] == i) res ++;
        }

        return res;
        
    }

private:
    int p[100000];

    int finds(int x){
        if (p[x] != x) p[x] = finds(p[x]);
        return p[x];
    }
};